Hard
Related Topics: Math / String
LeetCode Source

解題想法

在這個問題中，給定一個代表整數的字串 n，我們需要找到最接近的迴文數（不包括本身）。

所謂「最接近」是指兩個整數之間的絕對差值最小。如果有多個相同差值的迴文數，我們返回較小的那一個。

首先，我們可以通過將數字的前半部分鏡像，生成潛在的迴文候選者。

同時，我們也需要考慮前半部分加一或減一的情況，因為最接近的迴文可能出現在稍大或稍小的數字中。

對於像 "1" 這樣的特殊情況，最近的迴文數是 "0"。

此外，對於類似 "1000" 這樣的數字，可能的候選者還包括 "999" 和 "1001"。

我們將計算每個候選迴文與原數字之間的絕對差值，選擇差值最小的那個。

如果有差值相同的候選者，我們選擇數字較小的那個。

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Python

def closest_palindrome(n: str) -> str:
    length = len(n)
    if length == 1:
        return str(int(n) - 1)

    candidates = set()
    
    half = n[:(length + 1) // 2]
    half_num = int(half)
    
    for i in [-1, 0, 1]:
        new_half = str(half_num + i)
        if length % 2 == 0:
            candidate = new_half + new_half[::-1]
        else:
            candidate = new_half + new_half[:-1][::-1]
        candidates.add(candidate)
    
    candidates.add("9" * (length - 1))
    candidates.add("1" + "0" * (length - 1) + "1")
    
    candidates.discard(n)
    
    closest = None
    min_diff = float('inf')
    original_num = int(n)
    
    for candidate in candidates:
        candidate_num = int(candidate)
        diff = abs(candidate_num - original_num)
        if diff < min_diff or (diff == min_diff and candidate_num < int(closest)):
            min_diff = diff
            closest = candidate
    
    return closest

C++

在 C++ 中，將 char 轉為 int 時，我們需要減去 '0' 才能得到對應的整數值。

class Solution {
public:
    string closestPalindrome(string n) {
        int len = n.size();
        if (len == 1) return to_string(stoi(n) - 1);

        set<string> candidates;
        string half = n.substr(0, (len + 1) / 2);
        int half_num = stoi(half);

        for (int i = -1; i <= 1; ++i) {
            string new_half = to_string(half_num + i);
            string candidate;
            if (len % 2 == 0) {
                candidate = new_half + string(new_half.rbegin(), new_half.rend());
            } else {
                candidate = new_half + string(new_half.rbegin() + 1, new_half.rend());
            }
            candidates.insert(candidate);
        }

        candidates.insert(string(len - 1, '9'));
        candidates.insert("1" + string(len - 1, '0') + "1");

        candidates.erase(n);

        string closest;
        long min_diff = LONG_MAX;
        long original_num = stol(n);

        for (auto& candidate : candidates) {
            long candidate_num = stol(candidate);
            long diff = abs(candidate_num - original_num);
            if (diff < min_diff || (diff == min_diff && candidate_num < stol(closest))) {
                min_diff = diff;
                closest = candidate;
            }
        }

        return closest;
    }
};